package com.dubious.interview.euler;

public class Problem5 {

    private static final int factors = 20;

    /**
     * 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without
     * any remainder.
     * 
     * What is the smallest positive number that is evenly divisible by all of the numbers from 1 to
     * 20?
     */
    public static void main(String[] args) {
        //@formatter:off
        // brute force it: 
        //   take the number that is a multiple of all numbers; 
        //   subtract by 20 in a loop; 
        //   in each iteration of the loop determine whether the number is divisible by all numbers 1 to 20
        //@formatter:on

        //@formatter:off
//        long startValue = 1;
//        for (int i = 2; i <= factors; i++) {
//            startValue *= i;
//        }
//
//        System.out.println("Start Value: " + startValue);
//
//        long minDivisible = startValue;
//        for (long i = startValue - factors; i > 0; i -= factors) {
//            boolean isDivisible = true;
//            for (int j = 2; j <= factors; j++) {
//                if (i % j != 0) {
//                    isDivisible = false;
//                    break;
//                }
//            }
//
//            if (isDivisible) {
//                minDivisible = i;
//                System.out.println("New min divisible: " + i);
//            }
//        }
//
//        System.out.println("Minimum number divisible by all numbers 1 through 20: "
//                + minDivisible);
        //@formatter:on

        //@formatter:off
        // the bruce force method was going to take too long
        // but after running it with the output I noticed a pattern (confirmed with 10 factors):
        //    the difference between any new minDivisible and the previous is constant and is the actual minDivisible
        //@formatter:on

        long startValue = 1;
        for (int i = 2; i <= factors; i++) {
            startValue *= i;
        }

        System.out.println("Start Value: " + startValue);

        long minDivisible = 0;
        for (long i = startValue - factors; i > 0; i -= factors) {
            boolean isDivisible = true;
            for (int j = 2; j <= factors; j++) {
                if (i % j != 0) {
                    isDivisible = false;
                    break;
                }
            }

            if (isDivisible) {
                // found a match, let's take a difference with the start value
                minDivisible = startValue - i;
                break;
            }
        }

        System.out.println("Minimum number divisible by all numbers 1 through " + factors + ": "
                + minDivisible);
    }
}
